Word pattern II

Time: O(NxC(N-1,C-1)); Space: O(N+C); hard

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.(i.e if a corresponds to s, then b cannot correspond to s. For example, given pattern = “ab”, str = “ss”, return false.)

You may assume both pattern and str contains only lowercase letters.

Example 1:

Input: pattern = “abab”, str = “redblueredblue”

Output: True

Explanation:

  • “a”->“red”,“b”->“blue”

Example 2:

Input: pattern = “aaaa”, str = “asdasdasdasd”

Output: True

Explanation:

  • “a”->“asd”

Example 3:

Input: pattern = “aabb”, str = “xyzabcxzyabc”

Output: False

[2]:

class Solution1(object):
    """
    There are H(N-C,C-1) = C(N-1,C-1) possible splits of string,
    and each one costs O(n) to check if it matches the word pattern.
    Time: O(N*C(N-1,C-1)), N is length of str, C is unique count of pattern
    Space: O(N+C)
    """
    def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        w2p, p2w = {}, {}
        return self.match(pattern, str, 0, 0, w2p, p2w)


    def match(self, pattern, str, i, j, w2p, p2w):
        is_match = False
        if i == len(pattern) and j == len(str):
            is_match = True
        elif i < len(pattern) and j < len(str):

            p = pattern[i]
            if p in p2w:
                w = p2w[p]
                if w == str[j:j + len(w)]:  # Match pattern.
                    is_match = self.match(pattern, str, i + 1, j + len(w), w2p, p2w)
                # Else return false.
            else:
                for k in range(j, len(str)):  # Try any possible word
                    w = str[j:k+1]
                    if w not in w2p:
                        w2p[w], p2w[p] = p, w
                        is_match = self.match(pattern, str, i + 1, k + 1, w2p, p2w)
                        w2p.pop(w), p2w.pop(p)
                    if is_match:
                        break
        return is_match

[3]:

s = Solution1()

pattern = "abab"
str = "redblueredblue"
assert s.wordPatternMatch(pattern, str) == True

pattern = "aaaa"
str = "asdasdasdasd"
assert s.wordPatternMatch(pattern, str) == True

pattern = "aabb"
str = "xyzabcxzyabc"
assert s.wordPatternMatch(pattern, str) == False